package madixin.t547;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findCircleNum(int[][] M) {
        if (M == null || M.length < 1) {
            return 0;
        }

        Union union = new Union(M);
        return union.getCount();
    }
}
//并查集
class Union {
    private int[] parent;
    private int[] sz;

    public Union(int[][] M) {
        parent = new int[M.length];
        sz = new int[M.length];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        Arrays.fill(sz, 1);

        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M.length; j++) {
                if (i != j && M[i][j] == 1) {
                    union(i, j);
                }
            }
        }
    }

    private void union(int i, int j) {
        int pi = getParent(i);
        int pj = getParent(j);
        if (pi != pj) {
            if (sz[pi] > sz[pj]) {
                parent[pi] = pj;
                sz[pj] += sz[pi];
            } else {
                parent[pj] = pi;
                sz[pi] += sz[pj];
            }
        }
    }

    private int getParent(int i) {
        int p = parent[i];
        while (p != i) {
            i = p;
            p = parent[i];
        }
        return p;
    }

    public int getCount() {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < parent.length; i++) {
            set.add(getParent(i));
        }
        return set.size();
    }
}